package codeRandomThoughts.Test516最长回文子序列;

public class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] charS = s.toCharArray();
        int len = charS.length;

        //dp[i][j]:区间范围(i~j)左闭右闭的子串其最长回文子序列的长度
        int[][] dp = new int[len][len];

        //不用初始化 在递推的时候初始化即可

        //开始递推
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (charS[i] != charS[j]) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                } else {
                    if (j - i <= 1) {
                        dp[i][j] = j - i + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }

            }
        }

        return dp[0][len-1];
    }
}
